#include "heap.h"
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/* ******************************************************************
 *                DEFINICION DE LOS TIPOS DE DATOS                  *
 * *****************************************************************/

struct heap_t {
	void** datos;
	size_t tamanio;
	size_t cantidad;
	cmp_func_t cmpf;
};

/* ******************************************************************
 *            			PRIMITIVAS AUXILIARES						*
 * *****************************************************************/
					  /* FUNCIONES INTERNAS */
			  /* IMPLEMENTACION AL FINAL DEL ARCHIVO */

// Modifica al arreglo de manera tal que cumpla con las características
// de un heap de máximo.
// Pre: todos los parámetros son válidos.
// Post: se 'heapificó' el arreglo.
static void heapify (void* elementos[], size_t cant, cmp_func_t cmp);

// Intercambia los punteros.
// Pre: ambos son válidos.
// Post: los punteros fueron intercambiados.
static void swap_ptr (void **a, void **b);

// Compara el elemento en la posición 'p' con sus hijos subsiguientes
// y, en caso de ser menor, lo intercambia con el mayor de ellos. La función
// termina cuando el elemento es mayor que sus hijos y menor que su padre.
// Pre: todos los parámetros son válidos.
// Post: se le hizo un 'down_heap' al elemento del arreglo en 'p'.
static void down_heap (void* elementos[], size_t p, size_t cant, cmp_func_t cmp);

// Compara el elemento de la última posición con los padres que lo anteceden
// y, en caso de ser mayor, lo intercambia. La función termina cuando el
// elemento es menor que su padre y mayor que sus hijos.
// Pre: todos los parámetros son válidos.
// Post: se le hizo un 'up_heap' al último elemento del arreglo.
static void up_heap (void* elementos[], size_t cant, cmp_func_t cmp);

// Calcula y devuelve la posición en la que estaría el padre del elemento hallado
// en la posición pasada por parámetro. En caso de no tenerlo, devuelve -1.
// Post: se devolvió la posición del padre o -1.
static int heap_padre (size_t pos);

// Calcula y devuelve la posición en la que estaría el hijo izquierdo
// del elemento hallado en la posición pasada por parámetro.
// Si el resultado es igual o mayor a 'cant', devuelve -1.
// Post: se devolvió la posición del hijo izquierdo o -1.
static int heap_hijo_izq (size_t pos, size_t cant);

// Calcula y devuelve la posición en la que estaría el hijo derecho
// del elemento hallado en la posición pasada por parámetro.
// Si el resultado es igual o mayor a 'cant', devuelve -1.
// Post: se devolvió la posición del hijo derecho o -1.
static int heap_hijo_der (size_t pos, size_t cant);

// Redimensiona el heap al tamaño pasado por parámetro. Devuelve falso en caso de error.
// Pre: el heap fue creado.
// Post: se redimensionó el heap.
static bool heap_redimensionar (heap_t* heap, size_t tam);

/* ******************************************************************
 *					 IMPLEMENTACION DEL HEAP-SORT					*
 * *****************************************************************/

// Función de heapsort genérica. Esta función ordena mediante heap_sort
// un arreglo de punteros opacos, para lo cual requiere que se
// le pase una función de comparación. Modifica el arreglo "in-place".
// Notar que esta función NO es formalmente parte del TAD Heap.
void heapsort (void* elementos[], size_t cant, cmp_func_t cmp) {
	if ((!elementos) || (!cmp)) return;
	heapify (elementos, cant, cmp);
	
	size_t j = cant-1;
	while (j > 0) {
		swap_ptr (&elementos[0],&elementos[j]);
		j--;
		down_heap (elementos,0,j+1,cmp);
	}
}

/* ******************************************************************
 *         IMPLEMENTACION DE PRIMITIVAS DEL HEAP DE MAXIMO          *
 * *****************************************************************/

// Crea un heap. Recibe como único parámetro la función de comparación a
// utilizar. Devuelve un puntero al heap, el cual debe ser destruido con
// heap_destruir().
heap_t* heap_crear (cmp_func_t cmp) {
	heap_t* h = (heap_t*) malloc (sizeof(heap_t));
	if (!h) return NULL;
	
	h->tamanio = 30;
	h->cantidad = 0;
	h->cmpf = cmp;
	
	h->datos = (void**) calloc (h->tamanio,sizeof(void*));
	if (!(h->datos)) {
		free(h); return NULL;
	}
	return h;
}

// Elimina el heap, llamando a la función dada para cada elemento del mismo.
// El puntero a la función puede ser NULL, en cuyo caso no se llamará.
// Post: se llamó a la función indicada con cada elemento del heap. El heap
// dejó de ser válido.
bool heap_destruir (heap_t* heap, void destruir_elemento(void *e)) {
	if (!heap) return false;
	if (!heap_esta_vacio(heap)) {
		for (size_t i = 0; i < (heap->cantidad); i++) {
			if (destruir_elemento) destruir_elemento ( (heap->datos)[i] );
		}
	}
	free(heap->datos);
	free(heap);
	return true;
}

// Devuelve la cantidad de elementos que hay en el heap.
// Pre: el heap fue creado.
// Post: se devolvió la cantidad de elementos del heap.
size_t heap_cantidad (const heap_t* heap) {
	if (!heap) return 0;
	return (heap->cantidad);
}

// Devuelve true si la cantidad de elementos que hay en el heap es 0, false en
// caso contrario.
bool heap_esta_vacio (const heap_t* heap) {
	if (!heap) return false;
	if (heap_cantidad(heap) > 0) return false;
	return true;
}

// Agrega un elemento al heap. El elemento no puede ser NULL.
// Devuelve true si fue una operación exitosa, o false en caso de error. 
// Pre: el heap fue creado.
// Post: se agregó un nuevo elemento al heap.
bool heap_encolar (heap_t* heap, void* elem) {
	if (!heap) return false;
	
	(heap->datos)[heap->cantidad] = elem;
	(heap->cantidad)++;
	up_heap (heap->datos, heap->cantidad, heap->cmpf);
	
	if (heap->cantidad == heap->tamanio) {
		return heap_redimensionar (heap,(heap->tamanio)*3);
	}
	return true;
}

// Devuelve el elemento con máxima prioridad. Si el heap esta vacío, devuelve
// NULL. 
// Pre: el heap fue creado.
void* heap_ver_max (const heap_t* heap) {
	if (!heap) return NULL;
	return ( (heap->datos)[0] );
}

// Elimina el elemento con máxima prioridad, y lo devuelve.
// Si el heap esta vacío, devuelve NULL.
// Pre: el heap fue creado.
// Post: el elemento desencolado ya no se encuentra en el heap. 
void* heap_desencolar(heap_t* heap) {
	if (!heap) return NULL;
	if (heap_esta_vacio(heap)) return NULL;
	
	void* elem = (heap->datos)[0];
	(heap->datos)[0] = (heap->datos)[heap->cantidad-1];
	(heap->datos)[heap->cantidad-1] = NULL;
	(heap->cantidad)--;
	down_heap (heap->datos, 0, heap->cantidad, heap->cmpf);
	
	size_t porcentaje = (heap->cantidad) * 100 / (heap->tamanio);
	if ((porcentaje < 10) && (heap->cantidad > 5) ) {
		heap_redimensionar (heap,(heap->tamanio)/2);
	}
	return elem;
}

/* ******************************************************************
 *            IMPLEMENTACION DE PRIMITIVAS AUXILIARES				*
 * *****************************************************************/
 
// Modifica al arreglo de manera tal que cumpla con las características
// de un heap de máximo.
// Pre: todos los parámetros son válidos.
// Post: se 'heapificó' el arreglo.
static void heapify (void* elementos[], size_t cant, cmp_func_t cmp) {
	for (int i = cant-1; i >= 0; i--) down_heap(elementos,i,cant,cmp);
}

// Intercambia los punteros.
// Pre: ambos son válidos.
// Post: los punteros fueron intercambiados.
static void swap_ptr (void **a, void **b) {
	void *aux = *a;
	*a = *b;
	*b = aux;
}

// Función auxiliar de 'down_heap'. Realiza las sustituciones correspondientes.
// Pre: Todos los parámetros son válidos.
// Post: se realizaron las sustituciones.
static void heap_sustituciones (void* elementos[], size_t *j, int hizq, int hder, int comp_id, bool hay_izq) {
	if ((comp_id >= 0) && hay_izq) {
		swap_ptr (&elementos[*j],&elementos[hizq]);
		*j = hizq;
	}else {
		swap_ptr (&elementos[*j],&elementos[hder]);
		*j = hder;
	}
}

// Compara el elemento en la posición 'p' con sus hijos subsiguientes
// y, en caso de ser menor, lo intercambia con el mayor de ellos. La función
// termina cuando el elemento es mayor que sus hijos y menor que su padre.
// Pre: todos los parámetros son válidos.
// Post: se le hizo un 'down_heap' al elemento del arreglo en 'p'.
static void down_heap (void* elementos[], size_t p, size_t cant, cmp_func_t cmp) {
	if ((!elementos) || (!cmp)) return;
	size_t j = p;
	while (j < cant) {
		int hizq = heap_hijo_izq (j,cant);
		int hder = heap_hijo_der (j,cant);
		int compi = 0; int compd = 0; int comph = 0;
		bool hay_izq = false;
		if (hizq != -1) {
			compi = cmp (elementos[j],elementos[hizq]);
			hay_izq = true;
		}
		if (hder != -1) compd = cmp(elementos[j],elementos[hder]);
		if ((hizq != -1) && (hder != -1)) comph = cmp(elementos[hizq],elementos[hder]);
		
		if ((compi < 0) || (compd < 0)) {
			heap_sustituciones (elementos,&j,hizq,hder,comph,hay_izq);
		} else break;
	}
}

// Compara el elemento de la última posición con los padres que lo anteceden
// y, en caso de ser mayor, lo intercambia. La función termina cuando el
// elemento es menor que su padre y mayor que sus hijos.
// Pre: todos los parámetros son válidos.
// Post: se le hizo un 'up_heap' al último elemento del arreglo.
static void up_heap (void* elementos[], size_t cant, cmp_func_t cmp) {
	if ((!elementos) || (!cmp)) return;
	
	int j = cant-1;
	while (j > 0) {
		int padre = heap_padre (j);
		if (padre == -1) return;
		int comp_hp = cmp (elementos[j],elementos[padre]);
		if (comp_hp < 0) return;
		
		swap_ptr (&elementos[j],&elementos[padre]);
		j = padre;
	}
}

// Calcula y devuelve la posición en la que estaría el padre del elemento hallado
// en la posición pasada por parámetro. En caso de no tenerlo, devuelve -1.
// Post: se devolvió la posición del padre o -1.
static int heap_padre (size_t pos) {
	if (pos == 0) return -1;
	return ( (pos - 1) / 2 );
}

// Calcula y devuelve la posición en la que estaría el hijo izquierdo
// del elemento hallado en la posición pasada por parámetro.
// Si el resultado es igual o mayor a 'cant', devuelve -1.
// Post: se devolvió la posición del hijo izquierdo o -1.
static int heap_hijo_izq (size_t pos, size_t cant) {
	int a = ( 2 * pos + 1 );
	if ( a < cant ) return a;
	return -1;
}

// Calcula y devuelve la posición en la que estaría el hijo derecho
// del elemento hallado en la posición pasada por parámetro.
// Si el resultado es igual o mayor a 'cant', devuelve -1.
// Post: se devolvió la posición del hijo derecho o -1.
static int heap_hijo_der (size_t pos, size_t cant) {
	int a = ( 2 * pos + 2 );
	if ( a < cant ) return a;
	return -1;
}

// Redimensiona el heap al tamaño pasado por parámetro. Devuelve falso en caso de error.
// Pre: el heap fue creado.
// Post: se redimensionó el heap.
static bool heap_redimensionar (heap_t* heap, size_t tam) {
	void** datos_nuevo = realloc(heap->datos, tam * sizeof(void*));
    if ( (tam > 0) && (!datos_nuevo) ) return false;

    heap->datos = datos_nuevo;
    heap->tamanio = tam;
    return true;
}
